using System;
using System.Collections.Generic;
using System.Text;

namespace MyEditor
{
    class node :IEquatable<node>
    {
        public int name;
        public int tree;
        public node parent; //reference type
        public bool Equals(node other)
        {
            if (other == null)
            {
                if (this == null)
                    return true;
                else
                    return false;
            }

            return name.Equals(other.name);
        }

        public static node operator *(node n1, node n2) //overloading * as a assignment operator.
        {
            if (n2 != null)
            {
                node temp = n1;
                temp.name = n2.name;
                if (n2.parent != null)
                {
                    temp.parent = new node();
                    temp.parent = temp.parent * n2.parent;
                }
                else
                    temp.parent = null;
                temp.tree = n2.tree;
                return temp;
            }
            else
            {
                return null;
            }

        }
        
    }

    class edge : IEquatable<edge>
    {
        public node terminal1; //reference type
        public node terminal2; //reference type
        public float capacity;
        public bool Equals(edge other)
        {
            if ((other.terminal1.Equals(this.terminal1)) && (other.terminal2.Equals(this.terminal2)) || (other.terminal2.Equals(this.terminal1)) && (other.terminal1.Equals( this.terminal2)))
                return true;
            return false;
        }
    }

    class GraphCut
    {
        List<node> Slist = new List<node>();
        List<node> Tlist = new List<node>();
        List<node> Alist = new List<node>();
        Queue<node> queO = new Queue<node>();
        List<node> nodes;
        List<edge> edges;
        node S;
        node T;
        List<node> Stree = new List<node>();
        List<node> Ttree = new List<node>();

        public GraphCut(List<node> nodes, List<edge> edges, node S, node T)
        {
            this.edges = edges;
            this.nodes = nodes;
            this.S = S;
            this.T = T;
            Slist.Add(S);
            Tlist.Add(T);
            Alist.Add(S);
            Alist.Add(T);

        }

        void connect()
        {
            foreach (edge e in edges)
            {
                foreach (node n in nodes)
                {
                    if (e.terminal1.Equals(n))
                        e.terminal1 = n;
                    if (e.terminal2.Equals(n))
                        e.terminal2 = n;
                }
            }
        }

    


        void group()
        {
            foreach (node p in nodes)
            {
                if (p.tree == 1)
                    Stree.Add(p);
                else
                    Ttree.Add(p);
            }

        }

        public List<node> getStree()
        {
            return Stree;
        }

        public List<node> getTtree()
        {
            return Ttree;
        }

        public void doCut()
        {
            connect();
            while (true)
            {
                
                List<node> pathnode = new List<node>();
                pathnode = grow();
                if (pathnode.Count == 0)
                    break;
               
                augument(pathnode);
                
                adopt();
                
            }
            group();

        }

        void delfreenode()
        {
            foreach (node n in nodes)
            {
                if (n.parent == null)
                {
                    if (!((n.name == -1000) || (n.name == -2000)))
                    {
                        n.tree = 0;
                        delfreenode(n);
                    }
                }
            }


        }

        void delfreenode(node p)
        {
            foreach (node n in nodes)
            {
                if (n.parent != null)
                {
                    if (n.parent.Equals(p))
                    {
                        n.parent = null;
                        n.tree = 0;
                        delfreenode(n);
                    }
                }
            }
        }


        List<node> grow()
        {
            delfreenode();
            
            List<node> PathNodes = new List<node>();

            while (Alist.Count > 0)
            {
                for (int i = 0; i < Alist.Count; i++)
                {
                    if (Alist[i].tree == 0)
                        Alist.RemoveAt(i);
                }
                node p;
                p = Alist[0];
                List<node> neighbour = new List<node>();
                neighbour = this.findNeighbours(p);
                foreach (node q in neighbour)
                {
          
                    if (q.tree == 0)
                    {
                        if (p.parent != null)
                        {
                            if (!p.parent.Equals(q))
                            {
                                q.tree = p.tree;
                                q.parent = p;

                                bool has = false;
                                foreach (node t in Alist)
                                {
                                    if (t.Equals(q))
                                        has = true;
                                }
                                if (!has)
                                    Alist.Add(q);
                            }
                        }
                        else
                        {
                            q.tree = p.tree;
                            q.parent = p;

                            bool has = false;
                            foreach (node t in Alist)
                            {
                                if (t.Equals(q))
                                    has = true;
                            }
                            if (!has)
                                Alist.Add(q);
                        }
                    
                    }
                    if ((q.tree != 0) && (q.tree != p.tree))
                    {
                        PathNodes.Add(p);
                        PathNodes.Add(q);
                        //if (check(p) && check(q))
                           return PathNodes;
                        //else
                          //  continue;
                    }
                }
                for (int i=0;i<Alist.Count;i++)
                {
                    if (Alist[i].Equals(p))
                        Alist.RemoveAt(i);
                }
            }
            return PathNodes;
        }

        /*bool check(node p)
        {
            if (p.parent == null)
                return true;
            node temp = new node();
            temp = temp * p;
            node parent = new node();
            bool Ok=false;
            while (true)
            {
                parent = parent * temp.parent;
                if ((parent.parent == null) && ((parent.name == -1000) || (parent.name == -2000)))
                {
                    Ok = true;
                    break;
                }
                temp = temp * parent;

            }
            if (Ok)
                return true;
            else
                return false;
        }*/

        List<edge> findPath(List<node> pathNodes)
        {
            delfreenode();
            List<edge> path = new List<edge>();
            foreach (edge e in edges)
            {
                if ((e.terminal1.Equals(pathNodes[0]) && e.terminal2.Equals(pathNodes[1])) || (e.terminal2.Equals(pathNodes[0]) && e.terminal1.Equals(pathNodes[1])))
                {
                    if (!path.Contains(e))
                        path.Add(e);
                    break;
                }
            }

            foreach (node p in pathNodes)
            {

                if (p.parent == null)
                    continue;
                node temp = new node();
                temp = p;
                node parent = new node();

                while (true)
                {
                    parent = temp.parent;
                   
                    foreach (edge e in edges)
                    {
                        if (((e.terminal1.Equals(temp)) && (e.terminal2.Equals(parent)))|| ((e.terminal2.Equals(temp)) && (e.terminal1.Equals(parent))))
                        {
                            path.Add(e);
                            break;
                        }
                    }
                    if ((temp.name == -1000) || (temp.name == -2000))
                        break;

                    temp = parent;
                    
                }
            }

            return path;
            
        }

        void updateCapacity(float miniCapacity, List<edge> path)
        {
            foreach (edge e in path)
            {
                foreach (edge MapEdge in this.edges)
                {
                    if (MapEdge.Equals(e))   //change compare method to "equals" method
                        MapEdge.capacity -= miniCapacity;
                }
            }
        }


        void augument(List<node> pathNodes)
        {
            List<edge> path = new List<edge>();
            path = this.findPath(pathNodes);
            float miniCapacity = int.MaxValue;
            foreach (edge e in path)
            {
                if (e.capacity < miniCapacity)
                    miniCapacity = e.capacity;
            }
            this.updateCapacity(miniCapacity, path);
            foreach (edge e in path)
            {
                if (e.terminal1.tree == 1)
                {
                    if (e.terminal1.tree == e.terminal2.tree)
                    {
                        if (e.terminal1.parent == null || e.terminal2.parent == null)
                        {
                            if (e.terminal1.parent == null)
                            {
                                e.terminal2.parent = null;
                                queO.Enqueue(e.terminal2);
                            }
                            else
                            {
                                e.terminal1.parent = null;
                                queO.Enqueue(e.terminal1);

                            }

                        }
                        else
                        {
                            if (e.terminal1.parent.Equals(e.terminal2))
                            {
                                e.terminal1.parent = null;
                                queO.Enqueue(e.terminal1);
                            }
                            else
                            {
                                if (e.terminal2.parent.Equals(e.terminal1))
                                {
                                    e.terminal2.parent = null;
                                    queO.Enqueue(e.terminal2);
                                }
                            }
                        }

                    }
                }
                if (e.terminal1.tree == 2)
                {
                    if (e.terminal1.tree == e.terminal2.tree)
                    {
                        if (e.terminal1.parent == null || e.terminal2.parent == null)
                        {
                            if (e.terminal1.parent == null)
                            {
                                e.terminal2.parent = null;
                                queO.Enqueue(e.terminal2);
                            }
                            else
                            {
                                e.terminal1.parent = null;
                                queO.Enqueue(e.terminal1);

                            }

                        }
                        else
                        {
                            if (e.terminal1.parent.Equals(e.terminal2))
                            {
                                e.terminal1.parent = null;
                                queO.Enqueue(e.terminal1);
                            }
                            else
                            {
                                if (e.terminal2.parent.Equals(e.terminal1))
                                {
                                    e.terminal2.parent = null;
                                    queO.Enqueue(e.terminal2);
                                }
                            }
                        }

                    }

                }
            }


        }

        List<node> findNeighbours(node p)
        {
            foreach (node n in nodes)
            {
                if ((n.tree != 0) && (n.parent == null))
                {

                }
            }
            List<node> neighbour = new List<node>();
            foreach (edge e in this.edges)
            {
                if (e.capacity == 0)
                    continue;

                if (e.terminal1.Equals(p) && e.capacity > 0)
                {
                    if (!neighbour.Contains(e.terminal2))
                       
                   
                        neighbour.Add(e.terminal2);
                }

                if (e.terminal2.Equals(p) && e.capacity > 0)
                {
                    if (!neighbour.Contains(e.terminal1))

                        neighbour.Add(e.terminal1);
                }
            }
            return neighbour;

        }

        List<node> findZeroCapNei(node p)
        {
            foreach (node n in nodes)
            {
                if (n.tree != 0 && (n.parent == null))
                {

                }
            }
            List<node> neighbour = new List<node>();
            foreach (edge e in this.edges)
            {
                if (e.capacity == 0)
                    continue;
                if (e.terminal1.Equals(p) && e.capacity ==0)
                {
                    if (!neighbour.Contains(e.terminal2))
                        neighbour.Add(e.terminal2);
                }
                if (e.terminal2.Equals(p) && e.capacity == 0)
                {
                    if (!neighbour.Contains(e.terminal1))
                        neighbour.Add(e.terminal1);
                }
            }
            return neighbour;
        }



        void adopt()
        {
            while (queO.Count > 0)
            {
                node p;
                p = queO.Dequeue();
                List<node> neighbour;
                neighbour = this.findNeighbours(p);
                bool hasParent = false;
                for (int i = 0; i < neighbour.Count; i++)
                {
                    node q = neighbour[i];
                    if (q.tree == p.tree) 
                    {
                        bool done = false;
                        node temp= new node();
                        temp =  q;
                        while (true)
                        {
                            if (temp.name == -1000 || temp.name == -2000)
                            {
                                done = true;
                                break;
                            }
                            if (temp.parent == null)
                                break;
                            temp =  temp.parent;
                        }
                        if (done)
                        {
                            if (q.parent != null)
                            {
                                hasParent = true;
                                p.parent = q;
                                break;

                            }
                            
                        }
                    }
                }

                if (!hasParent)
                {
                    List<node> nghbs = this.findNeighbours(p);
                    foreach (node q in nghbs)
                    {
                        if (q.tree == p.tree)
                        {
                            Alist.Add(q);
                            if (q.parent != null)
                            {
                                if (q.parent.Equals(p))
                                {
                                    q.parent = null;
                                    queO.Enqueue(q);
                                }
                            }
                        }
                    }
                    nghbs.Clear();
                    nghbs = this.findZeroCapNei(p);
                    foreach (node q in nghbs)
                    {
                        if (q.tree == p.tree)
                        {
                            if (q.parent != null)
                            {
                                if (q.parent.Equals(p))
                                {
                                    
                                    q.parent = null;
                                    queO.Enqueue(q);
                                }
                            }
                        }

                    }

                    p.tree = 0;
                    for (int i = 0; i < Alist.Count; i++)
                    {
                        if (Alist[i].Equals(p))
                            Alist.RemoveAt(i);
                    }
                 

                }


            }
        }


    }

}
